//Write an efficient algorithm that searches for a value in an m x n matrix. Thi
//s matrix has the following properties: 
//
// 
// Integers in each row are sorted from left to right. 
// The first integer of each row is greater than the last integer of the previou
//s row. 
// 
//
// 
// Example 1: 
//
// 
//Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
//Output: true
// 
//
// Example 2: 
//
// 
//Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
//Output: false
// 
//
// 
// Constraints: 
//
// 
// m == matrix.length 
// n == matrix[i].length 
// 1 <= m, n <= 100 
// -104 <= matrix[i][j], target <= 104 
// 
// Related Topics 数组 二分查找 
// 👍 439 👎 0


package leetcode.editor.cn;

//Java：Search a 2D Matrix
class P74SearchA2dMatrix {
    public static void main(String[] args) {
        Solution solution = new P74SearchA2dMatrix().new Solution();
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        //1.通过斜角线的排序
        public boolean searchMatrixD(int[][] matrix, int target) {
            int row = matrix.length - 1;
            int col = 0;
            while (row >= 0 && col <= matrix[0].length - 1) {
                if (matrix[row][col] == target) {
                    return true;
                } else if (matrix[row][col] > target) {
                    row--;
                } else {
                    col++;
                }
            }
            return false;
        }
        //2.二分搜索,将二维矩阵转化为一维数组
        public boolean searchMatrix(int[][] matrix, int target) {
            if (matrix.length == 0 || matrix[0].length == 0) {
                return false;
            }
            int begin, mid, end;
            begin = mid = 0;
            int len1 = matrix.length, len2 = matrix[0].length;
            end = len1 * len2 - 1;
            while (begin < end) {
                mid = (begin + end) / 2;
                if (matrix[mid / len2][mid % len2] < target) {
                    begin = mid + 1;
                } else {
                    end = mid;
                }
            }
            return matrix[begin / len2][begin % len2] == target;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}